1. Field
Described embodiments relate generally to determining a password's strength and in particular to identifying the strength of patterns within a password.
2. Description of the Related Art
One security risk for online systems is the strength of a user's password. In many systems, passwords are stored as a hash of the password resulting from a hash function. A hash function is any algorithm or subroutine that maps large data sets of variable length, to smaller data sets of a fixed length. For example, a person's name, having a variable length, could be hashed to a single integer. The values returned by a hash function are called hash values, hash codes, hash sums, checksums or simply hashes. Given access to the hash and the hash function, the security of the account depends on the inability of an adversary to identify the password from the hash and the function. To make to it more difficult for adversaries to obtain passwords, many systems provide a password strength calculator that estimates the strength of a proposed password, on the assumption that a user will select a password that the calculator indicates as being higher strength.
One conventional way of approximating password strength is by estimating an amount of time that an adversary would take to determine the password if the adversary had access to the hashed password and hash function. This in turn is generally determined by the number of passwords an adversary would need to attempt before obtaining the password by trial and error by entering the passwords into the hash function. Since the hash function is generally chosen to take a non-negligible amount of time to provide a hash result, this approach assumes that a large number of attempts indicates a stronger password. That is, if the amount of time required to complete a large number of attempts exceeds the amount of time an adversary is likely to spend on an individual attack, then the password is determined to be a stronger password. Another way in which systems rate password strength is using simple rules such as the number of unique characters or the use of special characters.
However, since many users choose passwords that contain common patterns such as number-word-symbol, an adversary who attempts to break a password using patterns has a significantly higher chance of success. As a result many conventional password strength calculators will overestimate the strength of passwords by failing to recognize such patterns.